//给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
//
// 示例 1： 
//
// 输入: "babad"
//输出: "bab"
//注意: "aba" 也是一个有效答案。
// 
//
// 示例 2： 
//
// 输入: "cbbd"
//输出: "bb"
//  abcddcbb
// abcabccbacba
// Related Topics 字符串 动态规划 
// 👍 2500 👎 0


package leetcode.editor.cn;

public class LongestPalindromicSubstring {
    public static void main(String[] args) {
        Solution solution = new LongestPalindromicSubstring().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String longestPalindrome(String s) {
            String ans = "";
            int n = s.length();
            boolean[][] dp = new boolean[n][n];
            //dp[i][j] 在s[i]到s[j]是否回文串
            for (int i = 0; i < n; i++) {
                for (int j = 1; j < n; j++) {
                    if(i == 0){
                        //i=0的时候 肯定为true
                        dp[i][j] = true;
                    } else if(i == 1){
                        //i=1的时候 肯定为true
                        dp[i][j] = (s.charAt(i) == s.charAt(j));
                    } else {
                        dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
                    }
                    if(dp[i][j] && i+1>ans.length()){
                        ans = s.substring(i,i+j+1);
                    }
                }
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}